package dp;

/**
 * 二叉搜索树指的是  左子树节点 < root < 右子树节点的树
 * 因此考虑   针对每个节点遍历  每个节点做根节点的种类数之和就是 n个节点组成的总数
 *
 * 总的dp[i] = Σ dp[i-1] * dp[n - i]
 */
public class 不同的二叉搜索树_96 {

        public int numTrees(int n) {
            int[] dp = new int[n+1];

            dp[0] = dp[1] = 1;
            for(int i = 2; i<= n; i++) {
                // 求每个节点做根节点  所有节点种数和   dp[i] 初始值为0
                for(int j =1; j <= i; j++)
                    // 每个节点都轮询一遍  左子树种数乘以右子树的种数2
                    dp[i] += dp[j - 1] * dp[i - j];
            }
            return dp[n];
        }

}
